ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group00a.txt/000034_icon-group-sender _Tue Feb 15 13:07:26 2000.msg

Internet Message Format | 2001-01-03 | 7KB

Return-Path: <icon-group-sender>
Received: (from root@localhost)
    by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id NAA19253
    for icon-group-addresses; Tue, 15 Feb 2000 13:06:58 -0700 (MST)
Message-Id: <[e-mail]>
X-Authentication-Warning: agate.berkeley.edu: news set sender to <news> using -f
From: Jerry Leichter <[e-mail]>
X-Newsgroups: comp.lang.icon
Subject: Re: Co-expressions and backtracking in Icon (& Scheme)
Date: Tue, 15 Feb 2000 11:31:52 -0500
X-Trace: versa.smarts.com 950632312 3856 198.49.114.99 (15 Feb 2000 16:31:52 GMT)
X-Complaints-To: [e-mail]
To: John Paolillo <[e-mail]>
To: [e-mail]
Errors-To: [e-mail]
Status: RO

| ...The repeated mention of backtracking and co-routines
| in conjunction with one another, and the sudden
| realization that they may be similar in important ways
| (saving a computational state to resume its computation
| later), makes me wonder whether one might be able
| to implement backtracking with co-expressions (seems
| plausible, not that you would want to) and whether
| they share some aspect of their implementation in Icon.
| Can anyone explain the relationship between the two
| in Icon?  And can anyone speak to the relationship
| between the control aparatus of Scheme and that of
| Icon?

You are asking about complex issues about which many papers have been
written over many years.

Let's first look at backtracking and co-expressions.

Starting in the late 1960's, Ralph Griswold (and others) developed a
serious of languages named SNOBOL; the last and most successful was
SNOBOL4 (which is still available).  SNOBOL was based on pattern
matching, which required full backtracking.  (The string analysis
routines of Icon model the original SNOBOL string matching.)  SNOBOL was
fully interpreted in the original implementation (though partially
compiled implementations came later).  It used two stacks to implement
pattern matching.

In (I think) the late '70's, Griswold developed an experiment language
called SL5.  SL5 was inspired by a different approach to handling
backtracking:  It used coroutines.  (A coroutine is like a function, but
instead of simply returning, it can "suspend".  Later, you can "resume"
the coroutine where it last suspended.  This has a bit of a similarity
to multiple threads, but the usage is entirely different:  Only one
coroutine ever runs at a time, and all transfers of control are
explicitly programmed.)  Using coroutines, one could re-implement all
the SNOBOL pattern matching stuff in a very general and powerful way.
(SL5 also generalized a number of other ideas that were in SNOBOL, such
as "I/O bound variables".  But those are not of real interest here.)
Using the same general framework, one could use SL5 to go general
backtracking as well.

SL5 was an experiment to see how far one could push these ideas.  Icon
had its genesis in picking out some of the ideas in SL5 that had proved
to be useful.  Also, it was found that there was a much more efficient
way to implement those pieces of the coroutine model actually needed for
backtracking using stack manipulation.  This became the basis of the
Icon approach to backtracking.  (Actually, there was a short-lived
experimental language called CG - C with Generators - that provided
generators in C using the same stack manipulation trick.)  Icon focused
on fully integrating the backtracking model - and string scanning, the
algorithm that originally inspired it - into the rest of the language.
(In SNOBOL, you essentially had a goal-directed pattern matching
language embedded in a traditional imperative language.)  In fact,
coexpressions - a form of coroutine control bound to syntactic
expressions, rather than function calls - weren't in the original
version of Icon; they were added a number of years later.  Yes, you
could implement backtracking using coexpressions - that's going back to
the original SL5 model.  However, the result wouldn't be particularly
efficient.

Scheme and its continuations is the product of yet another long
evolution.  I won't try to go into a full history here; rather, I'll
suummarize what a continuation is.  (This is my own description; others
describe it in different ways.)  Think about what happens when you call
a function.  First, arguments are pushed on the stack.  Then control is
transfered to the function.  It computes, and eventually returns.

Well, actually, the implementation has to do more:  For return to work,
before transfering control, it has to pass the address to return to.
Let's make that explicit:  Let's pretend the return address is passed as
another argument.  Rather than a return, we just "go to" the return
address.  That *almost* simulates the effect of return.  The problem is
that the stack also has to be restored to what it was before the
function was called.  Implementations do that implicitly - they either
know how much space to clear off the stack, or save the actual old stack
address.  So let's make *that* explicit, to:  Pass as an argument a
special data structure, called a closure, that contains both the address
at which to continue, and what the stack should be set to.  (The reason
this is called a "closure" is that it "closes up" all the information
needed to continue execution of a function from where it was.  In fact,
that - not a pair of addresses - is the definition of a closure; real
implementations may need to worry about saving other machine state.)

So far, we've just come up with fancy names for things without adding
anything real to the language.  Things get interesting when we allow a
program to *save* one of these closure objects - and invoke it
repeatedly.  The result is very much like a coroutine (or coexpression)
- and it turns out that it's extremely powerful.  It also leads to
virtually incomprehensible programs unless very, very carefully used.
Usually, if you see a piece of code like:

    f();
    g();
    return;

you can reason that first f() is called, then g() is called, then we
return.  But if f() can "capture" the closure at its return point -
known as its continuation - then code elsewhere could jump back at the
call to g() any number of times, without f() running again.

Generally, explicit use of closures and continuations is discouraged as
a result:  They get used heavily inside of macros and as a compiler
technique, but few Scheme users ever use call-cc (call with current
continuation, which makes the current continuation into an explicit
argument).  However, it *is* possible to use these techniques to do what
arbitrary coroutines could do, including backtracking and generators.

                            -- Jerry